package LeetCode._02算法基础.day10递归回溯;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 21 - 19:01
 * @Description 给定一个候选人编号的集合candidates和一个目标数target，
 * 找出candidates中所有可以使数字和为target的组合。
 * candidates中的每个数字在每个组合中只能使用一次。
 * 注意：解集不能包含重复的组合。
 * @Version 中等
 */
public class _40组合总和2 {
    static int[] candidates = {10,1,2,7,6,1,5};
    static int target = 8;
    @Test
    public void test(){
        List<List<Integer>> res = combinationSum2(candidates, target);
        System.out.println(res);
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0, 0, false);
        return res;
    }
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    public void dfs(int[] candidates, int target, int sum, int index, boolean choosePre){
        if(sum == target){
            res.add(new ArrayList<>(list));
            return;
        }
        if(index >= candidates.length){
            return;
        }

        if(sum + candidates[index] <= target){
            //不取
            dfs(candidates, target, sum, index + 1, false);
            if(index > 0 && candidates[index - 1] == candidates[index] && !choosePre){
                return;
            }
            //取
            list.add(candidates[index]);
            dfs(candidates, target, sum + candidates[index], index + 1, true);
            list.remove(list.size() - 1);
        }

    }
}
